#include <stdio.h>
#include <stdlib.h>
#define MAX 50
typedef struct tree
{
    int data;
    struct tree *left, *right;
};
int weight[MAX];

tree *create(tree *&root, int data[], int low, int high)
{
    if (low <= high)
    {
        root = (tree *)malloc(sizeof(tree));
        int r = (weight[low] + weight[high + 1]) / 2;
        int i = low;
        while (weight[i + 1] < r)
        {
            i++;
        }
        root->data = data[i];
        root->left = root->right = NULL;
        create(root->left, data, low, i - 1);
        create(root->right, data, i + 1, high);
    }
}

int main()
{
    /*******************code*******************/
    int data[] = {1, 1, 2, 5, 3, 4, 4, 3, 5};
    int n = 9;
    tree *root = NULL;
    weight[0] = 0;
    for (int i = 1; i <= n; i++)
    {
        weight[i] = weight[i - 1] + data[i - 1];
    }
    create(root, data, 0, n - 1);

    /******************************************/
    printf("\n\n****************************\n");
    printf("Press Enter key to continue\n");
    getchar();
    return 0;
    /******************************************/
}
